# 20th of April 2010

import unittest
from string import punctuation as nondigit

def is_iterable_not_string(itr):
	'''return True if itr is iterable and not string, False otherways.'''
	try:
		iter(itr)
		assert(type(itr) != str)
	except:
		return False
	else:
		return True


def sisplit(string):
	'''split incoming string s in a list of string and integer. es "02dudee500." = [2, "dudee", 500, .]'''

	result = []
	n = -1
	s = '\n'
	for char in string:
		try:
			i = int(char)
			n = n==-1 and char or n+char
			
			if s!='\n': 
				result.append(s)
				s = '\n'
		except:
			s = s=='\n' and char or s+char
			
			if n!=-1:
				result.append(int(n))
				n = -1

	n!=-1 and result.append(int(n)) or None
	s!='\n' and result.append(s) or None
	return result

def maxsublen(array):
	'''return the max length of sublist in a list.'''
	l = map(len, array)
	return max(l)

def getColumns(matrix, i):
	'''get columns of a matrix implemented with list of list. Numbers are converted into string. Blank element are wrapper in ''\n es: [[1,2], ['a'], ['b',5],[0]] and 1 = ['2', '', 5, '']'''
	return [i<len(element) and str(element[i]) or ""
			  for element in matrix ]

def cast_to_int(char, null=-1):
	'''try cast in int, "" is converted to keyworded parameter null (-1 default)'''
	return char != '' and int(char) or null

def enumerate_and_sort(array):
	'''enumerate the list and sort the original one, es: [5, 1, 3] = [(1,1), (2,3), (0,5)]'''
	earray = list(enumerate(array))
	return sorted(earray, key=lambda x: x[1])

def mapsort(array, truthtable):
	'''sort with a truth table. es: ['a','b', 'c'] and [1,0,2] = ['b', 'a', 'c']'''
	if len(array)!=len(truthtable): raise ValueError
	retarray = []
	for i in truthtable:
		n = 0
		n = array[i]
		retarray.append(n)
	return retarray

def concat_sublist(matrix):
	'''concatenate sublist, es: [[1,2,'a'],['a', "foo"]] = ["12a", "afoo"]'''
	retval = []
	for element in matrix:
		complete_word = ""
		for word in element:
			complete_word+=str(word)
		retval.append(complete_word)
	return retval

def naturalsort(array):
	if not array: return []
	if not is_iterable_not_string(array):
		raise TypeError

	array  = list(map(lambda x: sisplit(x), array))
	for i in range(maxsublen(array), -1, -1):		
		narray = getColumns(array, i)
		try:
			narray = list(map(cast_to_int, narray))
		except: pass
		sortedarray = enumerate_and_sort(narray)
		maparray = list(map(lambda x: x[0], sortedarray))
		
		array = mapsort(array, maparray)

	return concat_sublist(array)


class Test_smalls(unittest.TestCase):
	def test_split_knowns(self):
		#TODO : autogenerated!!
		self.assertEquals(sisplit(""),[])
		self.assertEquals(sisplit("2a2"),[2, 'a', 2])
		self.assertEquals(sisplit("001"),[1])
		self.assertEquals(sisplit("foo"),["foo"])
		self.assertEquals(sisplit("asd-56"),["asd-", 56])
		self.assertEquals(sisplit("-1a0bn76ko11"),['-', 1, 'a', 0, 'bn', 76, "ko", 11])

	def test_findmaxsubs(self):
		l = [[], [1], [1,2], [1,2,3]]
		self.assertTrue(maxsublen(l)==3)

	def test_is_iterable(self):
		self.assertTrue(is_iterable_not_string([]))
		self.assertTrue(is_iterable_not_string({}))
		self.assertTrue(not is_iterable_not_string(""))
		self.assertTrue(not is_iterable_not_string(1))
	
	def test_get_columns(self):
		matrix = [[1,  2], 
			  ['a'  ], 
			  ['b',5],
			  [0]     ] 
		self.assertEqual(getColumns(matrix, 1), ['2', '',  '5', ''])	
		self.assertEqual(getColumns(matrix, 0), ['1', 'a', 'b', '0'])	

	def test_cast_to_int(self):
		self.assertEqual(cast_to_int('2'),2)
		self.assertEqual(cast_to_int(2),2)
		self.assertEqual(cast_to_int(''),-1)
		self.assertEqual(cast_to_int('', null=''),'')
		self.assertRaises(ValueError, cast_to_int, 'a')
		self.assertRaises(TypeError, cast_to_int, None)

	def test_enusort(self):
		a = [5, 1, 3] 
		self.assertEqual(enumerate_and_sort([]), [])
		self.assertEqual(enumerate_and_sort("foo"), [(0,'f'), (1,'o'), (2,'o')])
		self.assertEqual(enumerate_and_sort(a), [(1,1), (2,3), (0,5)])

	def test_mapsort(self):
		self.assertEqual(mapsort([],[]), [])
		self.assertEqual(mapsort(['a','b', 'c'],[1,0,2]), ['b', 'a', 'c'])
		self.assertRaises(ValueError,mapsort,[],[1])

	def test_concat(self):
		lst = [[1,2,'a'],['a', "foo"]]
		self.assertEqual(concat_sublist(lst), ["12a", "afoo"])

class Test_sort(unittest.TestCase):
	def test_final(self):
		values = ["B2", "Alpha 100", "Alpha 2", "Alpha 200", "Alpha 2A", "Alpha 2A-8000", "Alpha 2A-900"]
		knownsorted = ["Alpha 2", "Alpha 2A", "Alpha 2A-900", "Alpha 2A-8000", "Alpha 100", "Alpha 200", "B2"]
		result = naturalsort(values)
		self.assertEqual(knownsorted, result)

	def test_bad(self):
		self.assertTrue( naturalsort([]) == [])
		self.assertRaises(TypeError, naturalsort, "dudee")
		self.assertRaises(TypeError, naturalsort, 7)
unittest.main()
